﻿// 1349. 参加考试的最大学生数.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。

#include <iostream>
#include <vector>

using namespace std;
/*
https://leetcode.cn/problems/maximum-students-taking-exam/description/

给你一个 m * n 的矩阵 seats 表示教室中的座位分布。如果座位是坏的（不可用），就用 '#' 表示；否则，用 '.' 表示。
学生可以看到左侧、右侧、左上、右上这四个方向上紧邻他的学生的答卷，但是看不到直接坐在他前面或者后面的学生的答卷。
请你计算并返回该考场可以容纳的同时参加考试且无法作弊的 最大 学生人数。
学生必须坐在状况良好的座位上。


示例 1：
输入：seats = [["#",".","#","#",".","#"],
              [".","#","#","#","#","."],
              ["#",".","#","#",".","#"]]
输出：4
解释：教师可以让 4 个学生坐在可用的座位上，这样他们就无法在考试中作弊。

示例 2：
输入：seats = [[".","#"],
              ["#","#"],
              ["#","."],
              ["#","#"],
              [".","#"]]
输出：3
解释：让所有学生坐在可用的座位上。

示例 3：
输入：seats = [["#",".",".",".","#"],
              [".","#",".","#","."],
              [".",".","#",".","."],
              [".","#",".","#","."],
              ["#",".",".",".","#"]]
输出：10
解释：让学生坐在第 1、3 和 5 列的可用座位上。


提示：
seats 只包含字符 '.' 和'#'
m == seats.length
n == seats[i].length
1 <= m <= 8
1 <= n <= 8
*/


class Solution {
public:
    int dp[10][1 << 8];
    int mmap[10];

    void init(const vector<vector<char>>& seats) {
        memset(mmap,0,sizeof mmap);
        memset(dp, 0, sizeof dp);
        for (int i = 0; i < seats.size(); i++) {
            int state = 0;
            for (int j = 0; j < seats[0].size(); j++) {
                if (seats[i][j] != '.') { state += 1 << j; }
            }
            mmap[i] = state;
        }
    }

    bool check2(int a) {
        int curr = 0;
        while (a != 0) {
            if (a & 1 && curr == 1) return false;
            else if(a & 1 && curr == 0)curr = 1;
            else curr = 0;

            a >>= 1;
        }

        return true;
    }

    bool check(int a,int b,int idx) {
        if (idx != 0) {
            //检查a
            if ((a & mmap[idx - 1]) > 0) return false;
        }
        if ( (b & mmap[idx]) > 0) 
            return false;
        if (check2(a) &&  check2(b)  && check2(a | b)) { 
            return true; 
        }

        return false;
    }

    int GetAdd(int state, int idx) {
        int ret = 0;
        int desk = mmap[idx];
        while (state != 0) {
            if (state & 1 && (desk & 1) == 0) {
                ret++;
           }
            state = state>>1 ;
            desk =  desk>>1;
        }

        return ret;
    }

    int maxStudents(vector<vector<char>>& seats) {
        init(seats);
        
        for (int i = 0; i < seats.size(); i++) {
            int de = 1;
            for (int prev = 0; prev < (1 << seats[0].size()); prev++) {
                for (int curr = 0; curr < (1 << seats[0].size()); curr++) {
                    if (i == 0 && prev != 0) { continue; }
                    //检查和上排和左右是否有冲突 得到添加的人数
                    if (check(prev, curr,i) == true) {
                        int add = GetAdd(curr,i);
                        if (i == 0) {
                            dp[i][curr] = max(dp[i][curr], add);
                        }
                        else {
                            dp[i][curr] = max(dp[i][curr],dp[i - 1][prev]+add);
                        }
                    }
                }
            }
        }
        int ans = 0;
        for (int i = 0; i < (1 << seats[0].size()); i++) {
            ans = max(ans, dp[seats.size() - 1][i]);
        }

        return ans;
    }
};


int main()
{
    Solution  s;

    vector<vector<char>> v =
    { {'#', '.', '#', '#', '.', '#'},
        {'.', '#', '#', '#', '#', '.'},
        {'#', '.', '#', '#', '.', '#'}
    };

    s.maxStudents(v);


}

 